#include"cds_avl.h"
#include"cds_list.h"
#include<stdio.h>
#include<stdlib.h>

#ifdef __cplusplus
extern "C" {
#endif 

#define __add_size(tree) do{\
    (tree)->size++;\
    debug("添加到了%d个元素\n",(tree)->size);\
}while(0)

#define __sub_size(tree) do{\
    (tree)->size--;\
    debug("减少到了%d个元素\n",(tree)->size);\
}while(0)

//清空节点 
#define avl_clear_node(node) do{\
    node->parent = NULL; \
    node->left = NULL;\
    node->right = NULL; \
    node->height = 0;\
}while(0);

//获取节点的高度
#define avl_height(node) ((node)?(node)->height:-1)

//获取更高的子节点
#define avl_get_higher_child( node ) (\
    avl_height((node)->left)>avl_height((node)->right)?(node)->left:(node)->right)

//重新计算节点的高度
#define avl_node_height_recal(node) ({\
    int _old = avl_height(node);\
    if( node ){\
        int lh = avl_height(node->left);    \
        int rh = avl_height(node->right);   \
        node->height = lh>rh?lh+1:rh+1;         \
    }\
    _old!=node->height;\
})

//从node节点一直往上到树根，经过的节点统统更新高度
#define avl_update_height_up_to_root(node) do{\
    avl_node_t * _node = node;   \
    for(;_node; _node = _node->parent){\
        if(!avl_node_height_recal(_node))break; \
    } \
}while(0)

//获取节点的平衡因子,定义为左子节点高度减去右子节点高度, 差值在 [-1,1]之间表示该节点平衡
#define avl_node_balance(node) (avl_height((node)->left) - avl_height((node)->right))

//删除一个叶子节点的动作,根节点除外
#define avl_del_leaf(leaf) do{\
    if((leaf)->parent){\
        if((leaf)->parent->left == (leaf) )\
            (leaf)->parent->left = NULL; \
        else \
            (leaf)->parent->right = NULL;\
    }\
}while(0)

//将c (child)替换p (parent)的位置,注意:c,p均不能为NULL,c是p的独苗
#define avl_single_child_replace_parent(tree,p, c) do{\
    if( (tree)->root == (p) ){\
        (tree)->root = (c);\
    }else{\
        if((p)->parent->left == (p) ){\
            (p)->parent->left = (c);\
        }else{\
            (p)->parent->right = (c);\
        }\
    }\
    (c)->parent = (p)->parent;\
}while(0)

/* 
 * 交换两个节点的所有字段，及相关联的指针域更新
 * 
 *      相关的指针域有:
 *          其父节点的left或right指针之一,
 *          其左子节点的parent指针,
 *          其右子节点的parent指针
 *          如果没有父节点，则tree的root指针要更新
 */
#define avl_exchange_two_nodes(tree,n1,n2) do{\
    unsigned long _tmp;\
    for(int i=0;i<sizeof(avl_node_t)/sizeof(unsigned long);i++){\
        _tmp = ((unsigned long *)n1)[i];\
        ((unsigned long *)n1)[i] = ((unsigned long *)n2)[i];\
        ((unsigned long *)n2)[i] = _tmp;\
    }\
    avl_node_t * _arr[] = {n1,n2};\
    for(int i=0;i<2;i++){\
        avl_node_t * _it = _arr[i];\
        if(_it->left)\
            _it->left->parent = _it;\
        if(_it->right)\
            _it->right->parent = _it;\
        if(_it->parent){\
            if( _arr[1-i] ==_it->parent->left)\
                _it->parent->left = _it;\
            else \
                _it->parent->right = _it;\
        }else{\
            tree->root = _it;\
        }\
    }\
}while(0)

/**
 * 右旋函数:    p是父节点,c是p的左子节点;
 *              p表达一棵子树, 而g是这棵子树外的元素,但g可能有left或right指像这棵子树,
 *              p也可能是树的根节点，即不存在g这个节点,但树根节点由tree.root成员来记录 
 *   
 *   p不为树根节点的情况下:
 *
 *     g                       g
 *      \                       \
 *       \                       \
 *        p                       c
 *       / \                     / \ 
 *      c   pr?   ------->     cl?  p
 *     / \                         /  \
 *    cl? cr?                     cr? pr?
 *
 *   
 *   p为树的根节点的情况下:
 *
 *    tree.root         tree.root  
 *          \                  \
 *           \                  \
 *            _|                 _|
 *              p                  c
 *             / \                / \
 *            c   pr?  --->      cl? p
 *           / \                    / \
 *          cl? cr?                cr? pr?
 *
 *    思考: 要修改哪些指针,要修改哪些节点的高度?
 *     
 *      要动的指针:
 *          p.left 由 c变成了cr
 *          p.parent 由 g 变成了 c
 *          c.right 由 cr 变成了 p
 *          c.parent 由 p 变成了 g
 *          cr.parent 由 c 变成了 p
 *          p原来是树根的情况下: tree.root由p变成了c
 *          p原来不是树根的情况下:g.left或g.right 由 p 变成了 c 
 *     
 *      子树中要更新高度的节点:
 *          p,c,g,g往上直到根的节点 
 */
static void right_rotate(avl_tree_t* tree, avl_node_t * p,avl_node_t * c){
    debug("右旋---\n");
    avl_node_t * g = p->parent;
    //更新外指针
    if(g){
        if(g->left == p ){
            g->left = c;
        }else{
            g->right = c;
        }
    }else{
        tree->root = c;
    }
    c->parent = p->parent;
    p->parent = c;
    p->left = c->right;
    c->right = p; 
    
    if(p->left){
        p->left->parent = p;
    }
    
    //修改节点的高度,从p节点往上溯,更新高度
    avl_update_height_up_to_root(p);
}

/**
 * 左旋函数:    p是父节点,c是p的右子节点;
 *              p表达一棵子树, 而g是这棵子树外的元素,但g可能有left或right指像这棵子树,
 *              p也可能是树的根节点，即不存在g这个节点,但树根节点由tree.root成员来记录 
 *   
 *   p不为树根节点的情况下:
 *
 *     g                       g
 *      \                       \
 *       \                       \
 *        p                       c
 *       / \                     / \ 
 *      pr? c     ------->      p  cr?
 *         / \                 / \ 
 *        cl? cr?             pr? cl?
 *
 *   
 *   p为树的根节点的情况下:
 *
 *   tree.root               tree.root 
 *          \                       \
 *           \                       \
 *            _|                      _| 
 *              p                       c
 *             / \                     / \ 
 *            pr? c     ------->      p  cr?
 *               / \                 / \ 
 *              cl? cr?             pr? cl?
 *
 *
 *    思考: 要修改哪些指针,要修改哪些节点的高度?
 *     
 *      要动的指针:
 *          p.right 由 c变成了cl
 *          p.parent 由 g 变成了 c
 *          c.left 由 cl 变成了 p
 *          c.parent 由 p 变成了 g
 *          cl.parent 由 c 变成了 p
 *          p原来是树根的情况下: tree.root由p变成了c
 *          p原来不是树根的情况下:g.left或g.right 由 p 变成了 c 
 *     
 *      子树中要更新高度的节点:
 *          p,c,g,g往上直到根的节点 
 */
static void left_rotate(avl_tree_t * tree, avl_node_t * p, avl_node_t * c){
    debug("左旋---\n"); 
    avl_node_t * g = p->parent;
    if(g){
        if(g->left == p ){
            g->left = c;
        }else{
            g->right = c;
        }
    }else{
        tree->root = c;
    }
    c->parent = p->parent;
    p->parent = c;
    p->right = c->left;
    c->left = p;
    if(p->right){
        p->right->parent = p;
    }

    //修改节点的高度,从p节点往上溯,更新高度
    avl_update_height_up_to_root(p);
}

/* 
 *  左右双旋:  先左旋, 再右旋
 *             
 *    LR:  
 *
 *          G                  G                  C
 *       左/ \                / \                / \
 *        P   U     拎C左旋  C   U   拎C右旋    P   G
 *       / \右      --->    /        ----->    / \   \
 *      X   C              P                  X   N   U
 *         /              / \
 *        N              X   N
 *
 *
 *          G                  G                  C
 *       左/ \                / \                / \
 *        P   U     拎C左旋  C   U   拎C右旋    P   G
 *       / \右      --->    / \      ----->    /   / \
 *      X   C              P   N               X  N   U
 *           \            / 
 *            N          X
 *
 */
static void lr_rotate(avl_tree_t * tree, avl_node_t * g,avl_node_t * p, avl_node_t * c){
    debug("先左旋，后右旋---\n");
    left_rotate(tree, p,c);
    right_rotate(tree, g,c);
}

/* 
 *  右左双旋: 先右旋,再左旋 
 *   RL:
 *
 *          G                  G                    C
 *         / \右              / \                  / \
 *        U   P    拎C右旋   U   C     拎C左旋    G   P
 *         左/ \   ------>      / \    ------->  / \   \
 *          C   X              N   P            U   N   X
 *         /                        \
 *        N                          X
 *
 *          G                  G                    C
 *         / \右              / \                  / \
 *        U   P    拎C右旋   U   C     拎C左旋    G   P
 *         左/ \   ------>        \    ------->  /   / \
 *          C   X                  P            U   N   X
 *           \                    / \
 *            N                  N   X
 *
 */
static void rl_rotate(avl_tree_t * tree, avl_node_t * g, avl_node_t * p, avl_node_t * c ){
    debug("先右旋后左旋---\n");
    right_rotate(tree, p, c);
    left_rotate(tree, g, c);
}


/* 
 *  平衡函数:(在插入后失衡和删除后失衡均需调用本函数)
 *  node 参数为第一个可能不平衡的节点
 *      
 *      平衡原则:
 *                  左高右低的情况下:
 *                         LL:  右旋 
 *                         LR:  左右双旋(先左旋, 再右旋) 
 *                         RR:  左旋
 *                         RL:  右左双旋(先右旋, 再左旋)
 */
static void avl_balance(avl_tree_t * tree, avl_node_t * node){
    if(!node){
        debug("空节点传入了avl_balance函数!\n");
        return;
    }
    for(;node;node = node->parent ){

        //重算node的高度,理论上在此不需要重算,因为一旦经过旋转，那么往上溯直到根节点的高度都被更新过了
        avl_node_height_recal(node); 

        //获取祖孙三代g,p,c

        avl_node_t * g = node;
        //第一次循环有可能g节点没有子节点,所以它本身是平衡的，继续往上溯
        if(!g->left && !g->right)continue;

        avl_node_t * p = avl_get_higher_child(g);
        // c有可能是NULL,c为NULL时, 即p没有子节点,g只有p这一个子节点,那么g节点一定是平衡的,所以保证c为NULL的情况下不会参与旋转了   
        avl_node_t * c = avl_get_higher_child(p);  
         
        int gbalance = avl_node_balance(g);
        debug("lh=%d,rh=%d,gbalance=%d\n",avl_height(g->left),avl_height(g->right),gbalance); 
        if(gbalance >1 ){//如果左高右低而不平衡
            if(g->left == p  && p->left == c){
                //ll: 左左单右旋
                right_rotate(tree, g, p); 
            }else if( g->left == p && p->right == c ){
                //lr: 左右双旋
                lr_rotate(tree, g, p, c);
            }
        }else if(gbalance <-1){
            if( g->right == p && p->right == c ){
                //rr: 右右单左旋
                left_rotate(tree, g,p );
            }else {
                //rl: 右左双旋
                rl_rotate(tree, g, p, c); 
            }
        }
    }
}

//插入一个节点,如果插入失败，说明已经有相同key的数据存在，则返回已经存在于树中的这个节点指针
avl_node_t* avl_insert(avl_tree_t * tree, avl_node_t * node ){
    //清空新节点指针,很有必要的哦!
    avl_clear_node(node);
    //如果avl树为空，则插入的节点就作为根节点
    if(!tree->root){
        tree->root = node;
        __add_size(tree);
        return NULL;
    }
    //获取新插入节点的key
    unsigned long key = tree->keygen_func(node);
    avl_node_t * parent = tree->root;
    
    //循环迭代找到插入点
    while(1){
        unsigned long p_key = tree->keygen_func(parent);
        //已经有相同key的数据,不能再插入,这次插入失败,返回已经存在的节点指针
        if(p_key == key ){
            debug("相同key[%lu]的数据已经在avl树中存在!\n",key);
            return parent;
        }else if( key < p_key ){
            if(parent->left){
                //向左子树继续迭代
                parent = parent->left;
            }else{
                //定位成功,在左子节点上插入新节点
                parent->left = node;
                node->parent = parent;
                break;
            }
        }else{
            if(parent->right){
                //向右子树继续迭代
                parent = parent->right;
            }else{
                //定位成功,在右子节点上插入新节点
                parent->right = node;
                node->parent = parent;
                break;
            }
        }
    }
    //统计加1 
    __add_size(tree);
    //从node的parent节点往上一直到根节点去判断平衡
    avl_balance(tree,node->parent);
    return NULL;
}

//搜索: 二叉搜索树的搜索方法，很简单，用key比较，小就往左，大就往右，相等即搜到
avl_node_t * avl_search(avl_tree_t * tree, unsigned long key ){
    if( !tree->root ){
        debug("在空树中查找key:[%lu]!\n",key);
        return NULL;
    }
    //循环查找
    for(avl_node_t * node = tree->root;node;){
        unsigned long nkey = tree->keygen_func(node);
        if(key < nkey ){
            debug("遇到%lu,左拐\n",nkey); 
            node = node->left;
        }else if( key > nkey ){
            debug("遇到%lu,右拐\n",nkey); 
            node = node->right;
        }else{
            debug("遇到%lu,找到了\n",nkey); 
            return node;
        }
    }
    debug("没找到\n");
    return NULL;
}

//获取下一个节点
avl_node_t * avl_next(avl_node_t * node ){
    if(node->right)
        return avl_first(node->right);
    for(avl_node_t * parent = node->parent; parent ; node = parent, parent = parent->parent){
        if(parent->left == node)return parent;
    }
    return NULL;
}

//获取上一个节点
avl_node_t * avl_prev(avl_node_t * node ){
    return node->left?avl_last(node->left):NULL;
}

//删除一个节点
void avl_del(avl_tree_t * tree, avl_node_t * node ){

    //1, node有 左 右两个子节点,把它与左最大或右最小交换位置，变成只有一个子节点或没有子节点的情况
    if(node->left && node->right ){
        avl_node_t * rfirst = avl_first(node->right);
        avl_exchange_two_nodes(tree,node,rfirst);
    }

    /*node 没有子节点*/
    if( !node->left && !node->right ){
        //node是根节点,此时又没有任何子节点，则删除这个元素，更新统计量size,直接结束即可,不需要再平衡
        if(node== tree->root){
            tree->root = NULL;
            __sub_size(tree);
            return ;
        }else{
            //直接删掉node节点
            avl_del_leaf(node);
        }
    }
    // node 只有一个子节点
    else{
        //左或右子节点替上来
        avl_single_child_replace_parent(tree, node, (avl_node_t *)((unsigned long)node->right+(unsigned long)node->left));
    }
    
    //统计大小更新
    __sub_size(tree);

    //从node的parent开始往上直到树根节点做再平衡处理
    //avl_balance(tree, node->parent); 
}


//中遍遍历avl树
void avl_travel_middle(avl_tree_t * tree, travel_func_t travel){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    avl_node_t * node = avl_first(tree->root);
    while(node){
        travel(node);
        node = avl_next(node);
    }
}
            
//层次遍历avl树,用一个list来当队列使用
void avl_travel_level(avl_tree_t * tree,travel_func_t travel){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);

    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(avl_node_t *));
    *(avl_node_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;

    list_add_head(new, &head);
     
    while(!list_is_empty(&head)){
        struct list_head * out_node = list_del_last(&head);
        avl_node_t * node = *(avl_node_t **)(((char *)out_node)+sizeof(struct list_head));
        if(node->left){
            *(avl_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->left; 
            list_add_head(out_node,&head);
            out_node = NULL;  
        }
        if(node->right){
            if(!out_node){
                out_node = malloc(sizeof(struct list_head)+sizeof(avl_node_t *));
            }
            *(avl_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->right; 
            list_add_head(out_node,&head);
            out_node = NULL;
        }
        travel(node);
        if(out_node){
            free(out_node);
        }
    }
    
}

//清空avl树: 
void avl_clear(avl_tree_t * tree, destroy_func_t  destroy){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);
    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(avl_node_t *));
    *(avl_node_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;

    list_add_head(new, &head);
    while(!list_is_empty(&head)){
        struct list_head * out_node = list_del_last(&head);
        avl_node_t * node = *(avl_node_t **)(((char *)out_node)+sizeof(struct list_head));
        if(node->left){
            *(avl_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->left; 
            list_add_head(out_node,&head);
            out_node = NULL;  
        }
        if(node->right){
            if(!out_node){
                out_node = malloc(sizeof(struct list_head)+sizeof(avl_node_t *));
            }
            *(avl_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->right; 
            list_add_head(out_node,&head);
            out_node = NULL;
        }
        if(out_node){
            free(out_node);
            out_node = NULL;
        }
        destroy(node);
        __sub_size(tree);
    }
    tree->root = NULL;
}
#ifdef __cplusplus
}
#endif 
